package l.l.w.leetcode.BestTime2BuyAndSellStockWithTransactionFee;

/**
 * Created by llw on 2017/10/24.
 */
public class BestTime2BuyAndSellStockWithTransactionFee {
    public int maxProfit(int[] prices, int fee) {
        int l = prices.length;
        int[] hold = new int[l + 1]; //Hold the stock until day i;
        int[] notHold = new int[l + 1]; //Do not hold the stock until day i;
        hold[0] = Integer.MIN_VALUE;

        for (int i = 1; i <= l; i++) {
            hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i - 1] - fee);
            notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i - 1]);
        }

        return notHold[l];
    }

    public static void main(String[] args) {
        int[] prices={1, 3, 2, 8, 4, 9};
        int free = 2;
        int result = new BestTime2BuyAndSellStockWithTransactionFee().maxProfit(prices, free);

        System.out.println(result);
    }
}
